import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution241 {
    List<Integer> res;
    Deque<Integer> nums;
    Deque<Character> operators;

    public List<Integer> diffWaysToCompute(String expression) {
        res = new ArrayList<>();
        nums = new LinkedList<>();
        operators = new LinkedList<>();
        dfs(expression, 0);
        return res;
    }

    //回溯算法一定要记得复原全局变量哦
    void dfs(String s, int i) {
        if (i >= s.length()) {
            Deque<Integer> copyNums = new LinkedList<>(nums);
            Deque<Character> copyO = new LinkedList<>(operators);
            while (!copyO.isEmpty()) {
                copyNums.push(calculate(copyNums.pop(), copyNums.pop(), copyO.pop()));
            }
            res.add(copyNums.pop());
            return;
        }
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            int num = c - '0';
            i++;
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
                i++;
            }
            nums.push(num);
            dfs(s, i);
            nums.pop();
        } else {
            operators.push(c);
            dfs(s, i + 1);
            operators.pop();
            if (!operators.isEmpty()) {
                Integer b = nums.pop();
                Integer a = nums.pop();
                Character o = operators.pop();
                nums.push(calculate(b, a, o));
                dfs(s, i);
                nums.pop();
                operators.push(o);
                nums.push(a);
                nums.push(b);
            }
        }
    }

    Integer calculate(Integer b, Integer a, Character o) {
        if (o == '+') {
            return a + b;
        }
        if (o == '-') {
            return a - b;
        }
        if (o == '*') {
            return a * b;
        }
        return -1;
    }
}
